package homework;

import java.util.*;

public class hw496 {
    public static void main(String[] args) {
        int[] nums1 = {4,1,2};
        int[] nums2 = {1,3,4,2};
        int[] ans = Solution.nextGreaterElement(nums1, nums2);
        for (int i = 0;i< ans.length;i++){
            System.out.println(ans[i]);
        }
    }
}

class Solution {
    public  static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[nums1.length];
        // map用来记录栈顶和下一个最大值
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0;i < nums2.length; i++){
            while (!stack.isEmpty() && nums2[i] > stack.peek()){
                map.put(stack.pop(), nums2[i]);
            }
            // 往栈中添加新的元素
            stack.push(nums2[i]);
        }
        // 找不到下一个最大元素
        while (!stack.isEmpty()){
            map.put(stack.pop(), -1);
        }
        for(int m = 0; m<ans.length ;m++){
            ans[m] = map.get(nums1[m]);
        }
        return ans;
    }
}
